package org.huawei260.TiKu.ODsuanfa;

/**
 * @Author: qingle
 * @Date: 2024/10/28-16:11
 * @Description: 3004 【双指针】2024D-跳房子II
 * @version: 1.0
 */
public class D_2024D_3004__双指针_跳房子II { // c:90%
}

/**
 * #include <stdio.h>
 * #include <stdlib.h>
 * #include <string.h>
 * #include <limits.h>
 *
 * #define MAX_SIZE 10000
 *
 * typedef struct {
 *     int val;
 *     int idx;
 * } Step;
 *
 * void getResult(const int steps[], int steps_size, int count);
 *
 * int main() {
 *     int steps[MAX_SIZE];
 *     int steps_size = 0;
 *
 *     while(scanf("[%d", &steps[steps_size]) || scanf("%d", &steps[steps_size])) {
 *         steps_size++;
 *         if(getchar() != ',') break;
 *     }
 *
 *     int count;
 *     scanf("%d", &count);
 *
 *     getResult(steps, steps_size, count);
 *
 *     return 0;
 * }
 *
 * int cmp(const void* a, const void* b) {
 *     Step* A = (Step*) a;
 *     Step* B = (Step*) b;
 *
 *     return A->val != B->val ? A->val - B->val : A->idx - B->idx;
 * }
 *
 * int cmp2(const void* a, const void* b) {
 *     Step* A = (Step*) a;
 *     Step* B = (Step*) b;
 *
 *     return A->idx - B->idx;
 * }
 *
 * void getResult(const int steps[], int steps_size, int count) {
 *     Step newSteps[steps_size];
 *
 *     for(int i=0; i<steps_size; i++) {
 *         newSteps[i].val = steps[i];
 *         newSteps[i].idx = i;
 *     }
 *
 *     qsort(newSteps, steps_size, sizeof(Step), cmp);
 *
 *     int minStepIdxSum = INT_MAX;
 *     char* ans = "";
 *
 *     for(int i = 0; i < steps_size; i++) {
 *         // 剪枝优化
 *         if(newSteps[i].val > count && count > 0) break;
 *
 *         // 剪枝优化
 *         if(i > 0 && newSteps[i].val == newSteps[i-1].val) continue;
 *
 *         int l = i + 1;
 *         int r = steps_size - 1;
 *
 *         while(l < r) {
 *             // 剪枝优化，L,R指针指向值的目标和为count - i指针指向的值，而L指针指向的值 必然小于等于 R指针指向的值，
 *             // 因此L指针指向的值必然 <= 目标和/2，而R指针指向的值必然 >= 目标和/2
 *             int threshold = (count - newSteps[i].val) / 2;
 *
 *             if(newSteps[l].val > threshold || newSteps[r].val < threshold) break;
 *
 *             int stepValSum = newSteps[i].val + newSteps[l].val + newSteps[r].val;
 *
 *             if(stepValSum < count) {
 *                 l++;
 *             } else if(stepValSum > count) {
 *                 r--;
 *             } else {
 *                 // 剪枝优化
 *                 while (l < r - 1 && newSteps[r].val == newSteps[r-1].val) {
 *                     r--;
 *                 }
 *
 *                 int stepIdxSum = newSteps[i].idx + newSteps[l].idx + newSteps[r].idx;
 *
 *                 if(stepIdxSum < minStepIdxSum) {
 *                     minStepIdxSum = stepIdxSum;
 *
 *                     Step arr[] = {newSteps[i], newSteps[l], newSteps[r]};
 *                     qsort(arr, 3, sizeof(Step), cmp2);
 *
 *                     char res[100000] = {'\0'};
 *                     // res[0] = '[';
 *
 *                     for(int j = 0; j < 3; j++) {
 *                         Step step = arr[j];
 *
 *                         char tmp[1000];
 *                         sprintf(tmp, "%d", step.val);
 *
 *                         strcat(res, tmp);
 *
 *                         if(j < 2) {
 *                             strcat(res, ",");
 *                         } else {
 *                             // strcat(res, "]");
 *                         }
 *                     }
 *
 *                     ans = res;
 *                 }
 *
 *                 // 剪枝优化
 *                 while (l + 1 < r && newSteps[l].val == newSteps[l + 1].val) {
 *                     l++;
 *                 }
 *
 *                 l++;
 *                 r--;
 *             }
 *         }
 *     }
 *
 *     puts(ans);
 * }
 */